﻿#define _CRT_SECURE_NO_WARNINGS 1
//动态规划题目一：斐波那契数列：
//给你一个n让你求第n项的斐波那契数列为多少
//首先这个n最大为30，因为大于30的数，在斐波那契数列里面已经很大了
int fib(int n)
{
	//首先知道斐波那契数列的递推公式为f（n） = f（n-1）+f（n-2）
	//除了第一项和第二项的斐波那契数以外其它的斐波那契数，都可以使用这个递推公式求出来
	int f[31] = { 0,1 };//先初始化第一项和第二项斐波那契数列
	for (int i = 2; i <= n; i++)
	{
		f[i] = f[i - 1] + f[i - 2];
	}
	return f[n];//最后求出要求的斐波那契数列
}
//动态规划题目二：爬楼梯
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
//首先n最大为46
int climbStairs(int n)
{
	//先创建一个数组,这个数组里面储存的是从第0阶移动到第i阶所需要的方法数量
	//递推公式为f（i） = f（i-1）+f（i-2）
	int f[46] = {1,1};//首先f（0）代表从第0阶到第0阶方法只有一个
	//而f（1）从第0阶到第一阶方法也只有一个
	for (int i = 2; i <= n; i++)
	{
		f[i] = f[i - 1] + f[i - 2];//第i阶的台阶只能从第i-1和第i-2阶到达
	}
	return f[n];//这里返回的自然是从第0阶移动到第n阶的方法
}
int compare(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
//今日每日一题：数组中不等三元组的数目
int unequalTriplets(int* nums, int numsSize)
{
	//使用方法一：三循环暴力枚举
	/*int count = 0;
	for (int i = 0; i < numsSize; i++)
	{
		for (int j = i + 1; j < numsSize; j++)
		{
			for (int k = j + 1; k < numsSize; k++)
			{
				if (nums[i] != nums[j] && nums[j] != nums[k] && nums[k] != nums[i])
					count++;
			}
		}
	}*/
	//解法二：
	qsort(nums, numsSize, sizeof(int), compare);//将数组排序
	int res = 0, n = numsSize;
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n && nums[j] == nums[i]) {
			j++;
		}
		res += i * (j - i) * (n - j);
	}
	return res;
	//由题意可知，数组元素的相对顺序不影响结果，因此我们可以将数组 nums\textit{nums}nums 从小到大进行排序。排序后，数组中的相同元素一定是相邻的。当我们以某一堆相同的数 [i,j)[i, j)[i,j) 作为三元组的中间元素时，这堆相同的元素的左边元素数目为 iii，右边元素数目为 n−jn - jn−j，那么符合条件的三元组数目为：
//i×(j−i)×(n−j)i \times (j - i) \times (n - j)
//i×(j−i)×(n−j)
//对以上结果求和并返回最终结果。

}
//动态规划题目三
//泰波那契序列 Tn 定义如下：
//T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
int tribonacci(int n) {
	int m[38] = { 0,1,1 };//先将前三个泰波那契数赋值
	for (int i = 3; i <= n; i++)
	{
		m[i] = m[i - 1] + m[i - 2] + m[i - 3];//状态转移方程 
	}
	return m[n];
}
//跳房子的最小花费
//你一步可以跳1步或者是两步
#define min(a,b) ((a)<(b)?(a):(b)) 
int minCostClimbingStairs(int* cost, int costSize) {
	//首先创建dp数组
	//数组里面数的功能也就是到达i层所需要的最低花费
	int dp[1001] = { 0,0 };
	//因为可以选择从0或是1楼开始爬楼梯所以dp[0]和dp[1] 都为0
	//dp[i] = dp[i-1]+const[i-1]或是dp[i] = dp[i-2]+const[i-2]
	//而dp[i]的最小花费也就是取上面两者小的那一个
	for (int i = 2; i <= costSize; i++)
	{
		dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));
	}
	return dp[costSize];
}
//将数子变为0所需要的操作次数给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 
//力扣1342题目
int numberOfSteps(int num)
{
	//使用方法：动态规划使用状态转移方程
	//首先定义一个足够大的数组
	int f[1000001];//数组代表的是下标所代表的数变成0所需要的操作次数
	f[0] = 0;//显然从0变成0所需要的操作次数自然为0
	for (int i = 1; i <= 1000000; i++)
	{
		if (i % 2 == 1) {//代表i为奇数
			f[i] = f[i - 1] + 1;//这里当i为数的时候那么i-1自然是偶数偶数中储存的是
			//这个偶数变为0所需要的步骤，加上一个1自然也就是这个奇数变为0所需要的操作次数了
		}
		else//下标为偶数
		{
			f[i] = f[i / 2] + 1;//因为从i/2变为i也需要一步
		}
	}
	return f[num];
}
//动态规划题目打家劫舍
//力扣198打家劫舍
//一个数组你选取了一个数那么他相邻的两个数就不能选取，求解最后你选取和的最大值
int max(int a, int b)
{
	return a > b ? a : b;
}
int rob(int* nums, int numsSize) {
	//题目的要求就是我们进入了一间房间之后，不能进入它相邻的房间
	int f[101];//数组代表到第i个数为止所能储存的最大值
	f[0] = nums[0];//到第0个数为止，自然最大值也就是第0个数了
	for (int i = 1; i < numsSize; i++)
	{
		if (i == 1)
		{
			//第二个数
			f[i] = max(nums[0], nums[1]);//到1为止那么这里的最大值只能为二者选取大者
			//先确定数组前两个数的值，再通过下面的状态转移方程求解其它的值
		}
		else
			f[i] = max(f[i - 1], f[i - 2] + nums[i]);//如果i这个房子我偷了那么最大值也就是我偷前i-2个房子的最大值
		//再加上我现在偷的房子的值，如果i不选那么最大值也就是我偷前i-1个房子的最大值，这也即是状态1转移方程
	}
	return f[numsSize - 1];
}